#include <iostream>
#include <cmath>

using namespace std;

double mySqrt(double n, int prec) {
	double mid, low = 1, high = n;
	if (n < 1){	//!!!!!!!!!!!!!!!!!!very important
		low = n;
		high = 1;
	}
	double threshold = 1;

	while(prec--){
		threshold /= 10;
	}

	int times = 0;
	
	while (low <= high){
		mid = (low + high)/2;
		times++;
		
		if ( abs(mid * mid - n) < threshold ){/* mid * mid may be overflow? */
			cout <<"use " <<times <<" times" <<endl;
			return mid;
		}
		
		if (mid * mid < n){
			low = mid;
		} else {
			high = mid;
		}
	}
	return -1;
}

int sqrtTest(){
	double n = 2;
	int prec = 4;
	cout <<mySqrt(n, prec) <<endl;
	cout <<sqrt(n) <<endl;
	cin.get();
	return 0;
}